#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void Print(int* array, int size)
{
  for(int i = 0; i < size; i++){
    printf("%d ", array[i]);
  }
  printf("\n");
}

void Swap(int* pa1, int* pa2)
{
  int tmp = *pa1;
  *pa1 = *pa2;
  *pa2 = tmp;
}

void InsertSort(int* array, int size)
{
  for(int i = 1; i < size; i++){
    int end = i - 1;
    while(end >= 0){
      if(array[end] > array[i]){
        Swap(&array[i], &array[end]);
        i = end;
      }
      else break;
      end--;
    }
  }
}

void TestInsertSort()
{
  int* array = (int*)malloc(sizeof(int) * 100); 
  if(array == NULL){
    perror("malloc");
    return;
  }

  for(int i = 0; i < 100; i++){
    array[i] = rand() % 100 + 1;
  }

  InsertSort(array, 100);
  Print(array, 100);
  free(array);
}

int main()
{
  srand((unsigned long)time(NULL));
  TestInsertSort();
  return 0;
}
